\bigskip
\bigskip
{\magonebf 2.2 Strings (string)}     

Data type $string$ is the LEDA equivalent of $char*$ in \CC. The differences 
to the $char*$-type are that assignment, compare  and concatenation 
operators are defined and that argument passing by value works properly, 
i.e., there is passed a copy of the string and not only a copy of a pointer.
Furthermore a few useful operations for string manipulations are available. 


\def\name{$string$}
\def\type{$string$}

{\bf 1. Creation of a string }

a) \create s {}

b) \create s (char*\ p)

b) \create s (char\ c)

introduces a variable $s$ of type $string$. $s$ is initialized with the 
empty string (variant a), the string constant $p$ (variant b), or the 
one-character string ``$c$" (variant c).


\bigskip
{\bf 2. Operations on a string s}

\medskip
\+\cleartabs & \hskip 2.5truecm & \hskip 5truecm &\cr
\+\op int     length {}
                          {returns the length of string $s$}
\smallskip
\+\opa char\&   {int\ i}   
                          {returns the character at position $i$}
\+\nop                    {\precond{$0 \le i \le s$.length()$-$1} }
\smallskip
\+\opf string {int\ i,\ int\ j}
                          {returns the substring of $s$ starting at}
\+\nop                    {position $i$ and ending at position $j$}
\+\nop                    {\precond{$0 \le i \le j \le s$.length()$-$1} }
\smallskip
\+\op string  tail   {int\ i}       
                          {returns the last $i$ characters of $s$ }
\smallskip
\+\op string  head   {int\ i}       
                          {returns the first $i$ characters of $s$ }
\smallskip

\+\op int     pos    {string\ s_1}    
                        {returns the first position of $s_1$ in $s$ if $s_1$ is}
\+\nop                  {a substring of $s$, $-1$ otherwise}
\smallskip
\+\op int     pos    {string\ s_1,\ int\ i}    
                          {returns the first position of $s_1$ in $s$ right of}
\+\nop                    {position $i$ (-1 if no such position exists)}
\smallskip
\+\op string  insert {string\ s_1,\ int\ i}
                          {returns $s(0,i-1)$ + $s_1$ + $s(i,s.length()-1)$}
\+\nop                    {\precond{$0 \le i \le s$.length()$-$1} }
\smallskip
\+\op string  replace {string\ s_1,\ string\ s_2,\ int\ i=1} {}
\+\nop                    { returns the string created from $s$ by replacing }
\+\nop                    { the $i$-th occurence of $s_1$ in $s$ by $s_2$ }
\smallskip
\+\op string  replace\_all {string\ s_1,\ string\ s_2} {}
\+\nop                    { returns the string created from $s$ by replacing }
\+\nop                    { all occurences of $s_1$ in $s$ by $s_2$ }
\smallskip
\+\op string  replace {int\ i,\ int\ j,\ string\ s_1} {}
\+\nop                    { returns the string created from $s$ by replacing }
\+\nop                    { $s(i,j)$ by $s_1$ }
\smallskip
\+\op string  replace {int\ i,\ string\ s_1} {}
\+\nop                    { returns the string created from $s$ by replacing }
\+\nop                    { $s[i]$ by $s_1$ }
\smallskip
\+\op string del {string\ s_1,\ int\ i=1}  
                          { returns $s$.replace($s_1,"",i$) }
\smallskip
\+\op string del\_all {string\ s_1}         
                          { returns $s$.replace\_all($s_1,""$) }
\smallskip
\+\op string del {int\ i,\ int\ j}        
                          { returns $s$.replace($i,j,""$) }
\smallskip
\+\op string del {int\ i}                 
                          { returns $s$.replace($i,""$) }
\smallskip
\+\op void   read {istream\  I,\ char\ delim = '\ '} {}
\+\nop                    {reads characters from input stream $I$ into $s$}
\+\nop                    {until the first occurence of character $delim$}
\smallskip
\+\op void   read {char\  delim = '\ '}  
                          { read($cin$,$delim$) }
\smallskip
\+\op void   read\_line {istream\ I}       
                          { read($I$,'$\backslash$n') }
\smallskip
\+\op void   read\_line {}                 
                          { read\_line($cin$) }
\smallskip
\+\opb string    +  s_1  
                          {returns the concatenation of $s$ and $s_1$}
\smallskip
\+\opb string\&  += s_1  
                          {appends $s_1$  to $s$ and returns $s$}
\smallskip
\+\opb bool      == s_1  
                          {true iff $s$ and $s_1$ are equal}
\smallskip
\+\opb bool      != s_1  
                          {true iff $s$ and $s_1$ are not equal}
\smallskip
\+\opb bool      <  s_1  
                          {true iff $s$ is lexicographically smaller than $s_1$}
\smallskip
\+\opb bool      >  s_1  
                          {true iff $s$ is lexicographically greater than $s_1$}
\smallskip
\+\opb bool      <= s_1  
                          {returns $(s < s_1)\ ||\ (s == s_1)$}
\smallskip
\+\opb bool      >= s_1  
                          {returns $(s > s_1)\ ||\ (s == s_1)$}
\smallskip
\+\ops ostream\&  <<  O  
                          { writes string $s$ to the output stream $O$ }
\smallskip
\+\ops istream\&  >>  I  
                          { read($I$,'\ ') }

\bigskip
{\bf 3. Implementation }
\smallskip
Strings are implemented by \CC character vectors. All operations on a
string $s$ take time $O(s.length())$.


